Матч 343, Факторизуемое число (RefactorableNumber)

Дивизион 1, Уровень 3

Число называется факторизуемым, если оно делится на число его делителей. Например, следующие числа являются факторизуемыми: 1 (1 делитель), 12 (6 делителей), 9 (3 делителя). Числа 7 (2 делителя), 16 (5 делителей) не являются факторизуемыми.

В задаче требуется определить количество факторизуемых чисел на промежутке от low до high включительно.

Класс: RefactorableNumber

Метод: int count(int low, int high)

Ограничения: 1 £ low £ 2 * 10⁶, low £ high £ 2 * 10⁶.

Вход. Два числа low и high.

Выход. Количество факторизуемых чисел на промежутке от low до high включительно.

Пример входа

low	high
1	10
10	100
25	35

Пример выхода

4

12

0

РЕШЕНИЕ

факторизация

Объявим массив d длины 2000001, в который методом, аналогичным решету Эратосфена, занесем количество делителей натуральных чисел (d[i] равно количеству делителей числа i). Далее просматриваем все ячейки массива d от low до high и подсчитываем количество таких i, для которых i делится на d[i] (количество факторизуемых чисел от low до high).

ПРОГРАММА

#include <stdio.h>

#include <memory.h>

#define MAX 2000001

int d[MAX];

class RefactorableNumber

{

public:

int count(int low, int high)

{

int i, j, res;

memset(d,0,sizeof(d));

for(i = 1; i < MAX; i++)

for(j = i; j <= MAX; j += i) d[j]++;

res = 0;

for(i = low; i <= high; i++)

if (i % d[i] == 0) res++;

return res;

}

};